【题解】 [HNOI2012]永无乡 线段树+启发式合并 luoguP3224 | Qiuly's blog!

【题解】 [HNOI2012]永无乡 线段树+启发式合并 luoguP3224

Posted on | In | Comments:

实际上可以用平衡树做的但是不喜欢平衡树。

还是喜欢可爱的线段树，于是打了一发线段树合并。很久没有这样子的做题感觉了，真是美妙，思路清晰，交上去一遍过(窝不会告诉泥萌窝第一次交的时候忘关文件=。=)。

我们对于每一个点维护一个权值线段树，然后用并查集维护点与点之间的联通关系。对于一个连通块，该连通块的所有结点信息都保留在该连通块的 $root$ 上。

这样子我们合并两个岛的时候 $x,y$ ，可以直接将 $x$ 所在连通块的 $root$ (简称 $fx$ ) 和 $y$ 所在连通块的 $root$ (简称 $fy$ ) 合并起来，也就是将 $fy$ 的线段树并到 $fx$ 上去。这样子 $fx$ 就维护了这两个连通块的信息了，最后我们按照并查集的套路将 $fy$ 的父亲设为 $fx$ 即可。

询问就是基础操作，权值线段树就像主席树那样询问即可。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>

const int N=1e5+7;
const int Max=N*650;
const int inf=1e9+9;

template <typename _Tp> inline void IN(_Tp&x) {
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    if(flag) x=-x;
}

struct Seg_Tree {
    #define mid ((l+r)>>1)
    int cnt,rt[N],val[Max],lc[Max],rc[Max];
    inline void pushup(int x) {
        val[x]=val[lc[x]]+val[rc[x]];
    }
    void update(int&x,int l,int r,int pos) {
        if(!x) x=++cnt;
        if(l==r) {++val[x];return;}
        if(pos<=mid) update(lc[x],l,mid,pos);
        else update(rc[x],mid+1,r,pos);
        pushup(x);
    }
    int query(int x,int l,int r,int k) {
        if(l==r) return l;
        int th=val[lc[x]];
        if(k<=th) query(lc[x],l,mid,k);
        else return query(rc[x],mid+1,r,k-th);
    }
    int merge(int x,int y,int l,int r) {
        if(!x||!y) return x+y;
        if(l==r) {val[x]+=val[y];return x;}
        lc[x]=merge(lc[x],lc[y],l,mid),
        rc[x]=merge(rc[x],rc[y],mid+1,r);
        pushup(x);return x;
    }
}T;

int fa[N],pos[N],n,m,q;
int find(int x) {return fa[x]==x?x:fa[x]=find(fa[x]);}

int main() {
    IN(n),IN(m);
    for(int i=1,x;i<=n;++i)
        fa[i]=i,IN(x),pos[x]=i,T.update(T.rt[i],1,n,x);
    for(int i=1;i<=m;++i) {
        int u,v;IN(u),IN(v);
        int fu=find(u),fv=find(v);
        if(fu!=fv) T.merge(T.rt[fu],T.rt[fv],1,n),fa[fv]=fu;
    }
    IN(q);
    for(int i=1;i<=q;++i) {
        char op[2];int x,y,k;
        scanf("%s",op);
        if(op[0]=='B') {
            IN(x),IN(y);
            int fx=find(x),fy=find(y);
            if(fx!=fy) T.merge(T.rt[fx],T.rt[fy],1,n),fa[fy]=fx;
        } else if(op[0]=='Q') {
            IN(x),IN(k);
            int fx=find(x);
            if(T.val[T.rt[fx]]<k) printf("-1\n");
            else printf("%d\n",pos[T.query(T.rt[fx],1,n,k)]);
            /*我们query到的是第K大的权值而非岛屿的编号*/
            /*于是加个pos数组就好了*/
        }
    }
    return 0;
}

本文标题:【题解】 [HNOI2012]永无乡 线段树+启发式合并 luoguP3224

文章作者:Qiuly

发布时间:2019年04月04日 - 00:00

最后更新:2019年04月04日 - 16:32

原始链接:http://qiulyblog.github.io/2019/04/04/[题解]luoguP3224/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。